package written.test;

import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Dang Qi
 * @Date: 2021/4/10  14:55
 * @Description:
 */
public class Wangyi {
    public static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Wangyi wangyi = new Wangyi();
        int[] t = {1,2,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        ListNode tmp = new ListNode(0);
        ListNode head = tmp;
        for (int i : t){
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }
        t = new int[]{-1,2,3,0,2,5,6,3,6,8,9,5};
        tmp = new ListNode(0);
        ListNode head2 = tmp;
        for (int i : t){
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }
        ListNode rs = wangyi.minusList(head.next, head2.next);
        while(rs!=null) {
            System.out.print(rs.val+" ");
            rs = rs.next;
        }

    }
    public ListNode minusList (ListNode minuendList, ListNode subtrahendList){
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        ListNode node = minuendList;
        while (node!=null && s1.append(node.val)!=null) node = node.next;

        node = subtrahendList;
        while (node!=null && s2.append(node.val)!=null) node = node.next;

        boolean plus = false;
        String one, two;
        int resFlag = 1;
        boolean isExchange = false;
        if(s1.charAt(0)=='-'&&s2.charAt(0)=='-'){
            one = s2.substring(1,s2.length());
            two = s1.substring(1,s1.length());
        }else if(s1.charAt(0)=='-'&&s2.charAt(0)!='-'){
            plus = true;resFlag = -1;
            one = s1.substring(1, s1.length());
            two = s2.toString();
        }else if(s2.charAt(0)=='-'){
            plus = true;
            one = s1.toString();
            two = s2.substring(1, s2.length());
        }else{
            one = s1.toString();
            two = s2.toString();
        }
        if(one.compareTo(two)<0) {
            String s = one;
            one = two;
            two = s;
            isExchange = true;

        }
        int i = one.length()-1, j = two.length()-1;
        int jin = 0;
        int mul = plus ? 1: -1;
        ListNode head = new ListNode(0);

        while(i>=0||j>=0){
            int num =  jin;
            if(i>=0) num += one.charAt(i) - '0';
            if(j>=0) num += mul * (two.charAt(j) - '0');
            jin = num < 0 ? -1 : (num > 10 ? 1 : 0);
            num = (num + 10) % 10;
            ListNode tmp = new ListNode(num);
            tmp.next = head.next;
            head.next = tmp;
            i--;j--;
        }
        if(jin!=0){
            ListNode tmp = new ListNode(jin);
            tmp.next = head.next;
            head.next = tmp;
        }
        while (head.next!=null && head.next.val==0) head = head.next;
        head.next.val = resFlag * head.next.val * (isExchange&&!plus?-1:1);
        return head.next;
    }
    public int canCompleteRace (int[] e, int[] c) {
        // write code here
        int n = e.length;
        int i = 0;
        while (i<n){
            int leftE = 0;
            int cost = 0;
            int len = 0;
            while(len < n){
                int j = (i + len) % n;
                leftE += e[j];
                cost += c[j];
                if(leftE < cost) break;
                len++;
            }
            if(len==n) return i;
            i += i+len;
        }
        return -1;
    }

    public int billsChange(int[] bills){
        Map<Integer, Integer> map = new HashMap<>();
        map.put(5,2);
        map.put(10,0);
        map.put(20,0);
        int ans = 0;
        for(int i = 0; i < bills.length; i++){
            if(bills[i]==5){
                map.put(5, map.get(5)+1);
                ans++;
            }else if(bills[i] == 10) {
                if (map.get(5) == 0) break;
                map.put(10, map.get(10) + 1);
                map.put(5, map.get(5) - 1);
                ans++;
            }else{
                if(map.get(5)==0) break;
                if(map.get(10)==0){
                    if(map.get(5)<3) break;
                    map.put(5, map.get(5)-3);
                }else{
                    map.put(10,map.get(10)-1);
                    map.put(5, map.get(5)-1);
                }
                ans++;
            }
        }
        return ans;
    }
}
